package com.leetcode.code;

/**
 * 机器人一定会走m+n-2步，即从m+n-2中挑出m-1步向下走不就行了吗？即C（（m+n-2），（m-1））。
 * 排列组合问题 C(m+n-2,m-1)
 */

/**
 * 已发
 */
public class LeetCode0062Java {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println("结果：" + solution.uniquePaths(51, 9));
    }

    static class Solution {
        public int uniquePaths(int m, int n) {
            //C(m+n-2,n-1) = C(m+n-2,m-1)
            //一共要走的步数
            int sum = m + n - 2;
            //向下要走的步数
            int down = n - 1;
            double res = 1;
            // 阶乘化简到最后 就是这个表达式
            for (int i = 1; i <= down; i++) {
                res = res * (sum - down + i) / i;
            }
            return (int) res;
        }
    }
}
